using namespace std;
#include <vector>
#include <queue>

class Solution
{
    int m{}, n{};
    bool visit[101][101]{};
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
public:
    int nearestExit(const vector<vector<char>>& maze, const vector<int>& entrance)
    {
        m = maze.size(), n = maze[0].size();
        return bfs(maze, entrance[0], entrance[1]);
    }

    int bfs(const vector<vector<char>>& maze, int i, int j)
    {
        int ret = 0;
        queue<pair<int, int>> q;
        q.emplace(i ,j);
        visit[i][j] = true;
        while(!q.empty())
        {
            ret++;//要在这里++，因为是每层++，q不为空进入下一层
            int sz = q.size();
            while(sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int k=0; k<4; k++)
                {
                    int x = a+dx[k], y = b+dy[k];
                    if(x>=0 && x<m && y>=0 && y<n && visit[x][y]==false && maze[x][y]=='.')
                    {
                        visit[x][y] = true;
                        q.emplace(x, y);
                        if(x==0 || y==0 || x==m-1 || y==n-1)
                        {
                            return ret;
                        }
                    }
                }
            }
        }
        return -1;
    }
};